package special;

import java.util.*;

public class LeeCode_face_16_19 {
    public static void main(String[] args) {
        System.out.println(Arrays.toString(pondSizes(new int[][]{
                {0, 2, 1, 0},
                {0, 1, 0, 1},
                {1, 1, 0, 1},
                {0, 1, 0, 1}})));
    }
    private static int[] pondSizes(int[][] land) {
        int m = land.length, n = land[0].length;
        List<Integer> list = new ArrayList<>();
        int[][] dirs = new int[][]{{0, 1}, {0, -1}, {1, 0}, {-1, 0}, {1, -1}, {1, 1}, {-1, 1}, {-1, -1}};
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (land[i][j] == 0){
                    Deque<int[]> deque = new ArrayDeque<>();
                    deque.add(new int[]{i, j});
                    int count = 0;
                    land[i][j] = 1;
                    while (!deque.isEmpty()){
                        int size = deque.size();
                        for (int k = 0; k < size; k++) {
                            int[] p = deque.pop();
                            int x = p[0], y = p[1];
                            count++;
                            for (int[] dir : dirs) {
                                int nx = x + dir[0], ny = y + dir[1];
                                if (nx < 0 || nx >= m || ny < 0 || ny >= n || land[nx][ny] > 0){
                                    continue;
                                }
                                deque.offer(new int[]{nx, ny});
                                land[nx][ny] = 1;
                            }
                        }
                    }
                    list.add(count);
                }
            }
        }
        list.sort(Comparator.comparingInt(o -> o));
        int[] ans = new int[list.size()];
        for (int i = 0; i < list.size(); i++) {
            ans[i] = list.get(i);
        }
        return ans;
    }
}